package main.find;

import java.util.Arrays;

public class FibonacciFind extends BaseFind {

    public FibonacciFind(int[] array) {
        super(array);
        this.name = "斐波那契";
    }

    @Override
    public int find(int value) {
        int oldLength = array.length;

        int k = 3;
        int[] fiboArray = getFiboArray(k);
        while (oldLength > fiboArray[k - 1]) {
            fiboArray = getFiboArray(++k);
        }

        int newLength = fiboArray[k - 1] - 1;
        int[] newArray = Arrays.copyOf(array, newLength);
        for (int i = oldLength; i < newLength; i++) {
            newArray[i] = array[oldLength - 1];
        }

        int start = 0;
        int end = newArray.length - 1;
        while (start <= end) {
            int mid = getMid(start, fiboArray, k - 2);
            if (newArray[mid] > value) {
                end = mid - 1;
                k--;
            } else if (newArray[mid] < value) {
                start = mid + 1;
                k -= 2;
            } else {
                return Math.min(mid, oldLength - 1);
            }
        }
        return -1;
    }

    /**
     * 获取指定长度的斐波那契数组
     *
     * @param length 长度
     * @return 指定长度的斐波那契数组
     */
    public static int[] getFiboArray(int length) {
        int[] res = new int[length];
        res[0] = 1;
        res[1] = 1;
        for (int j = 2; j < res.length; j++) {
            res[j] = res[j - 1] + res[j - 2];
        }
        return res;
    }

    public int getMid(int start, int[] fiboArray, int fiboArrayIndex) {
        return start + fiboArray[fiboArrayIndex] - 1;
    }
}
